package com.datastructure.test.minsumoftriangle;

public class MinSumOfTriangle {

    int min = Integer.MAX_VALUE;
    public static void main(String[] args) {
        MinSumOfTriangle minSumOfTriangle = new MinSumOfTriangle();
//        int[][] data = {{2},{3,4},{6,5,7},{4,1,8,3}};
        int[][] data = {{1},{-1000,0}};
        minSumOfTriangle.minTrace(data);
    }

    public int minTrace (int[][] triangle) {
        // write code here
        if(triangle.length==1){
            return triangle[0][0];
        }
        dfs(triangle,0,0,0);
        return min;
    }

    private void dfs(int[][] triangle, int sum,int i, int j) {
        if(i>=triangle.length||j>=triangle[i].length){
            return;
        }
        if(j>i){
            return;
        }
        if(i==triangle.length-1){
            min=Math.min(min,sum+triangle[i][j]);
        }
        dfs(triangle,sum+triangle[i][j],i+1,j+1);
        dfs(triangle,sum+triangle[i][j],i+1,j);
    }

    public double Power(double base, int exponent) {
        double result = 1.00;
        boolean isNegative = exponent < 0;
        exponent=Math.abs(exponent);
        for(int i=0;i<exponent;i++){
            result*=base;
        }
        if(isNegative){
            return 1/result;
        }
        return result;
    }
}
